1) Field of the Invention
This invention pertains to the field of digital signal processing and, more particularly, to digital correlation.
2) Background of the Related Art
Correlators have been widely used in signal processing to measure the degree of correspondence between a data sequence and a predetermined pattern or reference sequence. In the case of one-dimensional digital signal processing, a correlation value y representing the correspondence between a sequence of data samples, d.sub.i, and a sequence of reference values, r.sub.i, is found by: ##EQU1##
Correlation is used in a number of applications including speech cognition, pattern recognition of printed matter in check-processing equipment, and communication system synchronization.
Correlators have been used in many communication systems to perform receiver clock synchronization. In that case, to facilitate synchronization, a communication transmitter and a communication receiver are each furnished with a reference sequence having a predetermined pattern. The communication transmitter transmits the reference sequence to facilitate synchronization of the receiver clock to the transmitted signal. The reference sequence is chosen to have good autocorrelation properties, e.g., a well-defined correlation peak and relatively low sidelobes.
FIG. 1 shows a communication receiver correlator operating with a correlation reference sequence, which is eight (8) bits in length, to produce a correlation peak at the time when the received data sequence matches the reference sequence. In the example of FIG. 1, it is assumed that each data sample is represented as an 8-bit two's-complement number having a value in the range of .+-.127. At each clock period, the last eight samples of input data d.sub.i (i=1,8) are multiplied sample by sample against the reference sequence bits r.sub.i (i=1,8) to produce a correlation value y. That is, y may have a maximum value of +1016 and a minimum value of -1016. The correlation value y is compared against a correlation threshold, y.sub.TH, and whenever y exceeds y.sub.TH, a correlation match is declared indicating that the correlation sequence has been received and the receiver is thereby synchronized to the transmitter.
Correlators have also been used in direct sequence spread-spectrum communication systems to detect received signals that have been spread for transmission using binary sequences called spreading codes. In this case, the transmitter and receiver are each furnished with a reference sequence having a predetermined pattern corresponding to the spreading code.
The transmitter spreads the original data signal to be transmitted with the spreading code to produce a spread spectrum signal. At the receiver, a despreading correlator recovers the original data signal by correlating the received signal against the reference sequence corresponding to the spreading code.
Correlators have been built using dedicated digital signal processors. However, these devices are limited by their processing speed. Thus, they may not be practical for high speed correlation, especially for very long reference sequences.
FIG. 2 is a block diagram of a conventional programmable digital correlator 100 of length n according to the prior art which may be used for receiver synchronization or for despreading a spread spectrum signal. The correlator 100 comprises a data delay line 101, reference sequence storage 103, multiplier stage 105, and an adder tree 107. The operation of this prior art correlator 100 will now be described.
During an initialization process, a reference sequence of reference values r.sub.i (i=1,n) is stored into the reference sequence storage 103. In the example correlator of FIG. 1, it is assumed that each reference sequence value r.sub.i is represented as a 1-bit binary value. On each reference clock cycle, a new reference sequence value r.sub.i is supplied to the reference sequence storage 103 in the correlator 100. The reference sequence storage 103 is comprised of an n-stage reference shift register further comprised of n 1-bit reference sequence registers 104.
A received data sequence of data samples d.sub.i (i=1,n) is supplied to the correlator 100 for correlation with the reference sequence. In the general case, each data sample d.sub.i is represented as an m-bit binary value. In the example correlator of FIG. 2, m=8. On each data clock cycle, a new data sample d.sub.i is supplied to the data delay line 101 in the correlator 100.
The data delay line 101 is configured as an n-stage data sequence shift-register. On each data clock cycle, a new data sample d.sub.1 is shifted byte-wise into first data Register-1 102 of the data delay line. The data sample d.sub.2 which had been stored in the first data Register-1 on the previous data clock cycle, is shifted into the second data Register-2. Similarly the data samples d.sub.i in all other data registers are each shifted one register to the right. The oldest data sample, d.sub.n+1, stored in the last data register Register-n exits the data delay line 101 and is discarded.
Correlation of the data sequence d.sub.i (i=1,n) with the reference sequence r.sub.i (i=1,n) is performed by first multiplying each data sample d.sub.i by a corresponding reference value r.sub.i in the multiplier stage 105. The multiplier stage 105 is comprised of n multipliers 106. The n multipliers 106 produce n correlation multiplication products, y.sub.i =d.sub.i *r.sub.i (i=1,n), each represented as an m-bit binary value, in this example m=8.
The n m-bit correlation multiplication products y.sub.i are then supplied to n/2 first stage adders 108 of the adder tree 107. Each first stage adder 108 adds two of the m-bit correlation multiplication products y.sub.i to produce an (m+1)-bit intermediate correlation sum z.sub.i. The n/2 first stage adders 108 produce n/2 intermediate correlation sums z.sub.i which are supplied to n/4 second stage adders in the adder tree 106. This process repeats until final stage adder 109 of the adder tree produces a single (m+log.sub.2 (n))-bit correlation value y. Thus, the adder tree consists of log.sub.2 (n) stages with a total number of n-1 adders.
An example of a prior art conventional correlator is the HSP45256, manufactured by Harris Corporation.
The prior art conventional programmable digital correlator 100 requires a large amount of circuitry. For example, consider a correlator of length n=128 for correlating 128 data samples represented as 8-bit numbers with a reference sequence of 128 1-bit numbers. The 128-stage data delay line requires one flip-flop for each bit to be stored. For the 8-bit data samples, the data delay line requires 8*128=1024 flip-flops. The reference sequence storage requires an additional 128 flip-flops, one for each bit in the reference sequence.
When designing with application specific integrated circuits (ASICs), the amount of logic is measured in gates, which are understood to be equivalent 2-input NAND gates. All other gates and flip-flops are converted to the required number of equivalent 2-input NAND gates. For example, a flip-flop is equivalent to at least six 2-input NAND gates.
The data delay line's 1024 flip-flops represent a logic requirement of 1024.times.6 gates=6144 equivalent 2-input NAND gates, and the reference storage requires 128.times.6 gates=768 equivalent 2-input NAND gates.
Each multiplier in the correlator must multiply a signed 8-bit data sample by a reference value, which is typically a 1-bit value. The 1-bit reference value can be an encoded value, with a value of `1` indicating `-1`, and a value of `0` indicating `+1`.
The result of the multiply is therefore either the same as the sample data (if the reference value is `0`), or it is minus the sample data value (if the reference value is `1`). Each multiplier can therefore be implemented as 8 XOR gates, and an 8 bit incrementor.
For gate count purposes, an XOR gate is equivalent to three 2-input NAND gates, and an incrementor requires about 4 gates per bit. The 8-bit by 1-bit multiplier requires 8.times.3 gates for the XOR gates, and the 8-bit incrementor requires 8.times.4 gates. Thus, each multiplier requires (8.times.3)+(8.times.4)=56 equivalent 2-input NAND gates. As there are 128 multipliers, this is a total of 128.times.56=7168 equivalent 2-input NAND gates.
The adder tree requires many more gates. In general, for a correlator of length n, n-1 adders are required. For the example correlator of length 128, with 8-bit data samples, the adder tree comprises 64 8-bit adders producing 9-bit results-, 32 9-bit adders producing 10-bit results, 16 10-bit adders producing 11-bit results, eight 11-bit adders producing 12-bit results, four 12-bit adders producing 13-bit results, two 13-bit adders producing 14-bit results, and one 14-bit adder producing a 15-bit result.
For gate count purposes, an adder requires 7 gates per bit. The adder tree for a correlator of length 128 therefore comprises a total of 1136 bits of adder, which require 1136*7=7952 equivalent 2-input NAND gates.
Thus, the programmable digital correlator of length 128, with 8-bit samples, requires a total of 1152 flip-flops and 15,120 other gates, or a total of at least 22032 gates, plus some small amount of glue logic.
In a spread spectrum system, a receiver may need to have many despreading correlators. For example, in a communication system having a central hub receiver which simultaneously communicates with many transmitters having different spreading codes, the receiver needs to have at least one despreading correlator for each spreading code which may be used. In this case, it is especially important to construct a correlator with an efficient circuit utilization.
For example, consider a spread spectrum receiver for a QPSK modulated spread spectrum signal with a spreading code sequence of length of 128 for both the I and Q waveforms. Assume further that the despreading receiver correlator operates on two samples per symbol to provide coarse timing information to the receiver, such that 256 8-bit samples of the received data are stored for correlation. If the correlator was constructed using the HSP45256 devices referenced above, each receiver would require at least 16 of these devices for each I or Q correlator. If the communication system uses 32 different spreading sequences which must be simultaneously detected, it would then require at least 16*2*32=960 of these devices.
In many low and medium volume applications, it is desired to implement programmable digital correlators using field programmable gate array (FPGA) devices. Unfortunately, a correlator such as the correlator 100 does not lend itself to an efficient construction using FPGA devices using conventional design practice.
For example, a Xilinx XC4025E FPGA has 1024 configurable logic blocks (CLBs). Each CLB contains two flip-flops, one secondary function generator, and two main function generators, each with four inputs and one output. For example, constructing just the 128-stage 8-bit data delay lines, required for two programmable digital correlators of length 128, would consume all 2048 flip-flops in this example Xilinx FPGA. Thus it is not possible according to the prior art to construct in the FPGA two conventional correlators 100 of length 128 for 8-bit data samples.
Indeed, simply fitting one such example correlator into a XILINX.RTM. 4025E would be difficult. The Xilinx XC4025E FPGA has a maximum of 25000 gates, of which typically 15000 gates may be able to be actually utilized using standard design practices. As shown above, the correlator of length 128, with 8-bit data samples, requires a minimum of 22032 gates.
Accordingly, it would be advantageous to provide a programmable digital correlator with a larger combination of shift register length and width than has been previously available in a single device. It would also be advantageous to provide a programmable digital correlator which is capable of simultaneously correlating input sampled data against two or more predetermined reference sequences. It would likewise be advantageous to provide a programmable digital correlator for a spread spectrum receiver which can process more than one sample per symbol of input data to provide coarse correlation peak timing information to be used by the receiver. It would further be advantageous to provide a programmable digital correlator which can operate at high speeds. Other and further objects and advantages will appear hereinafter.